lib/Mi manual de algoritmos/version_actual/src/geometria/line_line_intersection.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2 {\ttfamily \raggedright {
   3 \noindent
   4 \mbox{}\textit{\textcolor{Brown}{/*}} \\
   5 \mbox{}\textit{\textcolor{Brown}{\ \ Finds\ the\ intersection\ between\ two\ lines\ (Not\ segments!\ Infinite\ lines)}} \\
   6 \mbox{}\textit{\textcolor{Brown}{\ \ Line\ 1\ passes\ through\ points\ (x0,\ y0)\ and\ (x1,\ y1).}} \\
   7 \mbox{}\textit{\textcolor{Brown}{\ \ Line\ 2\ passes\ through\ points\ (x2,\ y2)\ and\ (x3,\ y3).}} \\
   8 \mbox{} \\
   9 \mbox{}\textit{\textcolor{Brown}{\ \ Handles\ the\ case\ when\ the\ 2\ lines\ are\ the\ same\ (infinite\ intersections),}} \\
  10 \mbox{}\textit{\textcolor{Brown}{\ \ parallel\ (no\ intersection)\ or\ only\ one\ intersection.}} \\
  11 \mbox{}\textit{\textcolor{Brown}{*/}} \\
  12 \mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{line$\_$line$\_$intersection}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{double}\ x0\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{double}\ y0\textcolor{BrickRed}{,}\ \ \ \textcolor{ForestGreen}{double}\ x1\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{double}\ y1\textcolor{BrickRed}{,} \\
  13 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textcolor{ForestGreen}{double}\ x2\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{double}\ y2\textcolor{BrickRed}{,}\ \ \ \textcolor{ForestGreen}{double}\ x3\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{double}\ y3\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  14 \mbox{}\textbf{\textcolor{RoyalBlue}{\#ifndef}}\ EPS \\
  15 \mbox{}\textbf{\textcolor{RoyalBlue}{\#define}}\ EPS\ \textcolor{Purple}{1e-9} \\
  16 \mbox{}\textbf{\textcolor{RoyalBlue}{\#endif}} \\
  17 \mbox{} \\
  18 \mbox{}\ \ \textcolor{ForestGreen}{double}\ t0\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{(}y3\textcolor{BrickRed}{-}y2\textcolor{BrickRed}{)*(}x0\textcolor{BrickRed}{-}x2\textcolor{BrickRed}{)-(}x3\textcolor{BrickRed}{-}x2\textcolor{BrickRed}{)*(}y0\textcolor{BrickRed}{-}y2\textcolor{BrickRed}{);} \\
  19 \mbox{}\ \ \textcolor{ForestGreen}{double}\ t1\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{(}x1\textcolor{BrickRed}{-}x0\textcolor{BrickRed}{)*(}y2\textcolor{BrickRed}{-}y0\textcolor{BrickRed}{)-(}y1\textcolor{BrickRed}{-}y0\textcolor{BrickRed}{)*(}x2\textcolor{BrickRed}{-}x0\textcolor{BrickRed}{);} \\
  20 \mbox{}\ \ \textcolor{ForestGreen}{double}\ det\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{(}y1\textcolor{BrickRed}{-}y0\textcolor{BrickRed}{)*(}x3\textcolor{BrickRed}{-}x2\textcolor{BrickRed}{)-(}y3\textcolor{BrickRed}{-}y2\textcolor{BrickRed}{)*(}x1\textcolor{BrickRed}{-}x0\textcolor{BrickRed}{);} \\
  21 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}det\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$}\ EPS\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  22 \mbox{}\ \ \ \ \textit{\textcolor{Brown}{//parallel}} \\
  23 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}t0\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$}\ EPS\ \textcolor{BrickRed}{$|$$|$}\ \textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}t1\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$}\ EPS\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  24 \mbox{}\ \ \ \ \ \ \textit{\textcolor{Brown}{//same\ line}} \\
  25 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}LINE}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{);} \\
  26 \mbox{}\ \ \ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
  27 \mbox{}\ \ \ \ \ \ \textit{\textcolor{Brown}{//just\ parallel}} \\
  28 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}NONE}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{);} \\
  29 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  30 \mbox{}\ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
  31 \mbox{}\ \ \ \ t0\ \textcolor{BrickRed}{/=}\ det\textcolor{BrickRed}{;} \\
  32 \mbox{}\ \ \ \ t1\ \textcolor{BrickRed}{/=}\ det\textcolor{BrickRed}{;} \\
  33 \mbox{}\ \ \ \ \textcolor{ForestGreen}{double}\ x\ \textcolor{BrickRed}{=}\ x0\ \textcolor{BrickRed}{+}\ t0\textcolor{BrickRed}{*(}x1\textcolor{BrickRed}{-}x0\textcolor{BrickRed}{);} \\
  34 \mbox{}\ \ \ \ \textcolor{ForestGreen}{double}\ y\ \textcolor{BrickRed}{=}\ y0\ \textcolor{BrickRed}{+}\ t0\textcolor{BrickRed}{*(}y1\textcolor{BrickRed}{-}y0\textcolor{BrickRed}{);} \\
  35 \mbox{}\ \ \ \ \textit{\textcolor{Brown}{//intersection\ is\ point\ (x,\ y)}} \\
  36 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}POINT\ \%.2lf\ \%.2lf}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{,}\ x\textcolor{BrickRed}{,}\ y\textcolor{BrickRed}{);} \\
  37 \mbox{}\ \ \textcolor{Red}{\}} \\
  38 \mbox{}\textcolor{Red}{\}} \\
  39 \mbox{}
  40 } \normalfont\normalsize